/*
package datastructure.day04;

import javax.lang.model.element.VariableElement;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

*/
/**
 * @Author Gan
 * @Date 2021/5/4 20:05
 * @Description:
 *//*

public class PreOrder<T extends Comparable<T>> {
    private Node root;
    private int size;

    //用递归实现前序遍历
    public List<T> preOrder() {
        List<T> list = new ArrayList<>();
        preOrder(list, root);
        return list;
    }

    private void preOrder(List<T> list, Node node) {
        if (node == null) {
            return;
        }
        // 前序遍历
        list.add(node.value);
        preOrder(list, node.left);
        preOrder(list, node.right);
    }

    //用栈实现前序遍历
    public List<T> preOrder1() {
        int count = 0;
        if (root == null) {
            return null;
        }
        //保存遍历结果
        List<T> list = new ArrayList<>();
        //将结点压入栈中
        Stack<Node> stack = new Stack<>();
        //根节点入栈
        stack.push(root);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            //尾插法
            list.add(count++,pop.value);
            if (pop.right != null){
                stack.push(pop.right);
            }
            if (pop.left != null){
                stack.push(pop.left);
            }
        }
        return list;
    }

    class Node {
        Node right;
        T value;
        Node left;

        public Node(Node right, T value, Node left) {
            this.right = right;
            this.value = value;
            this.left = left;
        }
    }
}
*/
